package medium;

import java.util.ArrayList;
import java.util.List;

public class Lc93 {
    class Solution {

        private List<String> ret = new ArrayList<>();
        public List<String> restoreIpAddresses(String s) {
            if (s.length() > 12) {
                return new ArrayList<>();
            }
            ArrayList<Integer> splits = new ArrayList<>();
            splits.add(-1);
            dfs(s, 0, 4, splits);
            return ret;
        }

        /**
         * 111
         * @param s 原始待切分字符串
         * @param index 当前位置
         * @param cnt 剩余切分次数
         * @param splits 切分位置记录
         */
        private void dfs(String s, int index, int cnt, List<Integer> splits) {
            // 边界
            if (cnt == 0 || index > s.length() - 1) {
                checkAndAddRet(s, splits);
                return;
            }
            // 选
            List<Integer> newSplits = new ArrayList<>(splits);
            newSplits.add(index);
            dfs(s, index + 1, cnt - 1, newSplits);

            // 不选
            dfs(s, index + 1, cnt, splits);
        }

        private void checkAndAddRet(String s, List<Integer> splits) {
            // System.out.println(splits.toString());
            if (splits.size() != 4) {
                return;
            }
            splits.add(s.length() - 1);
            List<Integer> pos = new ArrayList<>(4);
            for (int i = 1; i < splits.size(); i++) {
                // 字符串长度为0或大于3，退出
                if (splits.get(i) - splits.get(i - 1) == 0 || splits.get(i) - splits.get(i - 1) > 3) {
                    return;
                }
                String subString = s.substring(splits.get(i - 1) + 1, splits.get(i) + 1);
                int val = Integer.parseInt(subString);
                if (val == 0 && subString.length() > 1) {
                    return;
                }
                if (val > 0 && subString.startsWith("0")) {
                    return;
                }
                if (val > 255) {
                    return;
                }
                pos.add(val);
            }
            ret.add(pos.get(0) + "." + pos.get(1) + "." + pos.get(2) + "." + pos.get(3));
        }
    }
}
